package Aula10;

public class QuickRepetido {

	public void swap(int[] array, int i, int j) {
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}

	public int partition(int[] array, int begin, int end) {
		int ind = 0;
		
		int cont1 = 0;
		int index1 = ind;
		for (int i = 0; i < end; i++) {
			if (array[i] == array[index1]) {
				cont1++;
			}
		}
		ind ++;
		
		while(ind < array.length - 1){
			int cont2 = 0;
			int index2 = ind;
			for (int i = 0; i < end; i++) {
				if (array[i] == array[index2]) {
					cont2++;
				}
			}

			if (cont1 < cont2) {
				cont1 = cont2;
				index1 = index2;
			}
			ind ++;
		}
		
		int index = index1;
		int pivot = array[index];
		swap(array, index, end);
		
		for (int i = index = begin; i < end; ++i) {
			if (array[i] <= (pivot)) {
				swap(array, index++, i);
			}
		}
		swap(array, index, end);
		return (index);
	}

	public void qsort(int[] array, int begin, int end) {
		if (end > begin) {
			int index = partition(array, begin, end);
			qsort(array, begin, index - 1);
			qsort(array, index + 1, end);
		}
	}

	public void sort(int[] array) {
		qsort(array, 0, array.length - 1);
	}

}
